package leetcode;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

//leetcode 496
public class Code010_NextGreaterElement {

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            boolean reach = false;
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == nums1[i]) {
                    reach = true;
                }
                if (nums2[j] > nums1[i] && reach) {
                    res[i] = nums2[j];
                    break;
                }
                res[i] = -1;
            }

        }
        return res;
    }

    public static int[] nextGreaterElement2(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];

        LinkedList<Integer> stack = new LinkedList();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > stack.peek()) {
                int cur = stack.pop();
                map.put(cur, nums2[i]);
            }
            stack.push(nums2[i]);
        }
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            map.put(cur, -1);
        }
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }

    /**********************  leetcode 503, 循环数组下一个更大元素         ************************/

    // 不好的代码，by me
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[nums.length];
        LinkedList<Integer> stack = new LinkedList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % n]) {
                if (!map.containsKey(stack.peek())) {
                    int cur = stack.pop();
                    map.put(cur, i % n);
                } else {
                    stack.pop();
                }
            }
            stack.push(i % n);
        }
        // 最后留在栈里的都是-1，这里脱裤子放屁了
        while (!stack.isEmpty()) {
            if (!map.containsKey(stack.peek())) {
                int cur = stack.pop();
                map.put(cur, -1);
            } else {
                stack.pop();
            }

        }
        for (int i = 0; i < nums.length; i++) {
            res[i] = map.get(i) == -1 ? -1 : nums[map.get(i)];
        }
        return res;
    }

    // 好的代码
    public static int[] nextGreaterElements2(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < len * 2 - 1; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % len]) {
                res[stack.pop()] = nums[i % len];
            }
            stack.push(i % len);
        }
        return res;

    }

    /*************leetcode 556,*******************/
    public static int nextGreaterElementIII(int n) {
        String s = String.valueOf(n);
        char[] nums = s.toCharArray();
        Deque<Integer> stack = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                int cur = stack.pop();//i-1
                // 找到i右边比他大的中最小的那个数下标，交换
                for (int j = nums.length - 1 ; j >= cur; j--) {
                    if(nums[i] < nums[j]){
                        swap(nums, i,j);
                        break;
                    }
                }
                reverse(nums, cur);
                try{
                    return Integer.valueOf(String.valueOf(nums));

                }catch (Exception e){
                    return -1;
                }

            }
            stack.push(i);
        }
        return -1;

    }

    public static void swap(char[] a, int i, int j) {
        char temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    public static void reverse(char[] a, int start){
        int i = start, j = a.length -1;
        while(i < j){
            swap(a, i++, j--);
        }
    }

    public static void main(String[] args) {
//        int[] nums1 = {4,1,2}, nums2 = {1,3,4,2};
//        int[] res = nextGreaterElement2(nums1, nums2);
//        for(int cur : res){
//            System.out.print(cur+" ,");
//        }
//        int[] nums = {1, 2,2,2, 1};
//        int[] res = nextGreaterElements(nums);
//        for (int cur : res) {
//            System.out.print(cur + ", ");
//        }

        int res = nextGreaterElementIII(12443322);
        System.out.println(res);
    }

}
